#include <iostream>

using namespace std;
#include <vector>
#include <string>
#include <unordered_map>

class Solution {
public:
    string modifyString(string s) {
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] == '?')
            {
                int left = 1;
                int right = 1;
                if (i == 0) left = 0;
                if (i == s.size() - 1) right = 0;
                for (int j = 'a'; j <= 'z'; j++)
                {
                    if (j != s[i - left] && j != s[i + right])
                        s[i] = j;
                }
            }
        }
        return s;
    }
};


class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        int count = 0;
        count += duration;
        for (int i = 1; i < timeSeries.size(); i++)
        {
            if (timeSeries[i] - timeSeries[i - 1] >= duration)
            {
                count += duration;
            }
            else
            {
                count += timeSeries[i] - timeSeries[i - 1];
            }
        }
        return count;
    }
};


class Solution {
public:
    string convert(string s, int numRows) {
        string ret;

        if (numRows == 1)
            return s;

        for (int i = 0; i < numRows; i++)
        {
            int j = i;
            while (j < s.size())
            {
                ret.push_back(s[j]);
                if (j + (numRows - i) * 2 - 2 < s.size() && i != 0 && i != numRows - 1)
                {
                    ret.push_back(s[j + (numRows - i) * 2 - 2]);
                }
                j += numRows * 2 - 2;
            }
        }
        return ret;
    }
};


class Solution {
public:
    string countAndSay(int n) {
        string ret = "1";
        while (--n)
        {
            string tmp;
            int left = 0, right = 0;
            for (; right < ret.size(); right++)
            {
                if (ret[left] != ret[right])
                {
                    tmp.push_back(right - left + 48);
                    tmp.push_back(ret[left]);
                    left = right;
                }
            }
            tmp.push_back(right - left + 48);
            tmp.push_back(ret[left]);
            ret = tmp;
        }
        return ret;
    }
};


class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        unordered_map<char, int> hash1;
        unordered_map<char, char> hash2;
        hash2['c'] = 'k', hash2['r'] = 'c', hash2['o'] = 'r', hash2['a'] = 'o', hash2['k'] = 'a';
        for (auto e : croakOfFrogs)
        {
            if (e == 'c')
                if (hash1[hash2[e]] > 0) hash1[e]++, hash1[hash2[e]]--;
                else hash1[e]++;
            else
                if (hash1[hash2[e]] == 0) return -1;
                else hash1[hash2[e]]--, hash1[e]++;
        }
        if (hash1['c'] || hash1['r'] || hash1['o'] || hash1['a']) return -1;
        else return hash1['k'];
    }
};